package TreePackage;

import java.util.ArrayList;
import java.util.List;

import static TreePackage.TreeNode.*;

/**
 * @author Lzm
 * @version 1.0
 */
public class BinaryTree2 {
  public static void main(String[] args) {
    TreeNode node1 = new TreeNode(1);
    TreeNode node2 = new TreeNode(2);
    TreeNode node3 = new TreeNode(3);
    TreeNode node4 = new TreeNode(4);
    BinaryTree2 tree = new BinaryTree2(node1);
    tree.root.setLeft(node2);
    tree.root.setRight(node3);
    node2.setLeft(node4);
    List<Integer> result = new ArrayList<>();

    preList(tree.root,result);
    System.out.println(result);

    middleList(tree.root,result);
    System.out.println(result);

    lastList(tree.root,result);
    System.out.println(result);
  }


  private TreeNode root;

  public BinaryTree2() {
  }

  public BinaryTree2(TreeNode root) {
    this.root = root;
  }

  /**
   * 获取
   * @return root
   */
  public TreeNode getRoot() {
    return root;
  }

  /**
   * 设置
   * @param root
   */
  public void setRoot(TreeNode root) {
    this.root = root;
  }

  public String toString() {
    return "BinaryTree2{root = " + root + "}";
  }

}
class TreeNode{
  private int value;
  private TreeNode left; // 左节点
  private TreeNode right; // 右节点

  public TreeNode() {
  }

  public TreeNode(int value) {
    this.value = value;
  }

  /**
   * 获取
   * @return value
   */
  public int getValue() {
    return value;
  }

  /**
   * 设置
   * @param value
   */
  public void setValue(int value) {
    this.value = value;
  }

  /**
   * 获取
   * @return left
   */
  public TreeNode getLeft() {
    return left;
  }

  /**
   * 设置
   * @param left
   */
  public void setLeft(TreeNode left) {
    this.left = left;
  }

  /**
   * 获取
   * @return right
   */
  public TreeNode getRight() {
    return right;
  }

  /**
   * 设置
   * @param right
   */
  public void setRight(TreeNode right) {
    this.right = right;
  }

  public String toString() {
    return "TreeNode{value = " + value + "}";
  }


  /*定义前序遍历*/
  /*前序遍历*/
  /*递归三部曲
   * 1. 确定递归函数的参数和返回值 (二叉树)
   * 2. 确定终止条件
   * 3. 确定单层逻辑
   * */
  public static void preList(TreeNode Root, List<Integer> result) {
    /*判断根节点是否为空*/
    if (Root == null) {
      return;
    }
    /*List添加元素*/
    result.add(Root.getValue());
    /*左子节点遍历*/
    if (Root.left != null) {
      preList(Root.left, result);
    }
    if (Root.right != null) {
      /*右子节点遍历*/
      preList(Root.right, result);
    }
  }

  /*定义中序遍历*/
  public static void middleList(TreeNode Root, List<Integer> result) {
    /*判断根节点是否为空*/
    if (Root == null) {
      return;
    }
    if (Root.left != null) {
      middleList(Root.left, result);
    }
    /*List添加元素*/
    result.add(Root.getValue());
    /*左子节点遍历*/
    if (Root.right != null) {
      /*右子节点遍历*/
      middleList(Root.right, result);
    }
  }

  /*定义后序遍历*/
  public static void lastList(TreeNode Root, List<Integer> result) {
    /*判断根节点是否为空*/
    if (Root == null) {
      return;
    }
    if (Root.left != null) {
      lastList(Root.left, result);
    }

    /*左子节点遍历*/
    if (Root.right != null) {
      /*右子节点遍历*/
      lastList(Root.right, result);
    }
    /*List添加元素*/
    result.add(Root.getValue());
  }
}
